package com.chapter3.search;

import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Queue;

/** 
 * @ClassName: BST 
 * @Description: 二叉查找树 
 * @author minjun minjun@bw30.com
 * @date 2015-2-19 上午10:34:42 
 *  
 */
public class BST<K extends Comparable<K>,V> extends AbstractST<K, V>{
	
	private Node root;

	private class Node{
		int sz;
		Node left,right;
		K k;
		V v;
		public Node(int sz, K k, V v) {
			this.sz=sz;
			this.k = k;
			this.v = v;
		}
	}
	
	@Override
	public void put(K k, V v) {
		root=put(k,v,root);
	}

	/** 
	* @Title: put 
	* @Description:递归插入元素
	* @param @param k
	* @param @param v
	* @param @param root2
	* @param @return    设定文件 
	* @return Node    返回添加的指定节点
	* @throws 
	*/ 
	private Node put(K k, V v, Node r) {
		if(r==null) return new Node(1, k, v);
		int c=k.compareTo(r.k);
		if(c==0){
			r.k=k;r.v=v;
		}else if(c>0){
			r.right=put(k, v, r.right);
		}else{
			r.left=put(k, v, r.left); 
		}
		r.sz=size(r.left)+size(r.right)+1;
		return r;
	}

	@Override
	public V get(K k) {
		if(k==null) throw new RuntimeException("key不能为空");
		return get(k,root);
	}

	/** 
	* @Title: get 
	* @Description: 递归获取值
	* @param @param k
	* @param @param root2
	* @param @return    设定文件 
	* @return V    返回类型 
	* @throws 
	*/ 
	private V get(K k, Node r) {
		if(r==null) 	return null;
		int c=k.compareTo(r.k);
		if(c==0) 		return r.v;
		else if(c>0) 	return get(k,r.right);
		else 			return get(k,r.left);
	}
	
	public K min(){
		return min(root).k;
	}
	
	public K max(){
		return max(root).k;
	}
	
	/** 
	* @Title: rank 
	* @Description: 排名
	* @param @param k
	* @param @return    设定文件 
	* @return int    返回类型 
	* @throws 
	*/ 
	public int rank(K k){
		return rank(k,root);
	}
	
	private int rank(K k, Node node) {
		//如果没找到，那么表示不存在，返回0
		if(node==null) 
			return 0;
		int c=k.compareTo(node.k);
		if(c==0)
			return size(node.left);//如果找到了该元素，那么直接返回他的排名，也就是所有比他小的元素的数量
		else if(c>0) 
			return 1+size(node.left)+rank(k, node.right);//如果元素在右边，那么先把左边的（目前小于指定key的）全部收集起来，然后再递归查找右边的
		else 
			return rank(k, node.left);//如果该元素在左边，那么继续递归查找该元素的左边元素，直至找到为止，并获取该元素的排位
	}

	private Node max(Node node) {
		if(node.right==null) return node;
		return max(node.right);
	}

	private Node min(Node node){
		if(node.left==null) return node;
		return min(node.left);
	}
	
	@Override
	public int size() {
		return size(root);
	}
	
	public int size(Node node){
		return node==null?0:node.sz;
	}

	@Override
	public void delete(K k) {
		root=delete(k,root);
	}

	/** 
	* @Title: delete 
	* @Description: 删除指定节点
	* @param @param k
	* @param @param root2    设定文件 
	* @return Node    返回删除后，跟在他后面的节点
	* @throws 
	*/ 
	private Node delete(K k, Node node) {
		if(node==null) return null;
		int c=k.compareTo(node.k);
		if(c==0){
			//如果右边的节点已经为空，那么返回左边的节点，用来衔接上面一个等待递归结果的节点：如c->f->e之间删除了f,f右边没有节点，那么就返回e，也就成了c->e
			if(node.right==null) return node.left;
			//与上同理
			if(node.left==null) return node.right;
			//存储要被删除的节点
			Node original=node;
			//获取右边最小元素用来替换被删除节点
			node=min(original.right);
			//拿到了右边最小元素之后，就把他从原来的位置上删除掉，并重置右边节点
			node.right=deleteMin(original.right);
			//重置左边节点
			node.left=original.left;
		}else if(c>0){
			node.right= delete(k, node.right);
		}else{
			node.left=delete(k, node.left);
		}
		node.sz=size(node.left)+size(node.right)+1;
		return node;
	}

	/** 
	* @Title: deleteMin 
	* @Description: 删除指定节点下的最小元素
	* @param @param node
	* @param @return    设定文件 
	* @return Node    返回类型 
	* @throws 
	*/ 
	private Node deleteMin(Node node) {
		if(node==null) return null;
		if(node.left==null) return node.right;
		node.left=deleteMin(node.left);
		node.sz=size(node.left)+size(node.right)+1;
		return node;
	}

	@Override
	public boolean contains(K k) {
		return false;
	}

	@Override
	public Iterator<K> iterator() {
		return new MyIterator();
	}
	
	/**
	 * 
	* @Title: print 
	* @Description: 打印 
	* @param     设定文件 
	* @return void    返回类型 
	* @throws
	 */
	public void print(){
		print(root);
	}
	
	private void print(Node node){
		if(node==null) return;
		print(node.left);
		System.out.println(node.k);
		print(node.right);
	}
	
	private class MyIterator implements Iterator<K>{
		
		private Queue<K> queue;

		public MyIterator() {
			queue=new PriorityQueue<K>();
			fill(root);
		}
		
		private void fill(Node node){
			if(node==null) return;
			fill(node.left);
			queue.add(node.k);
			fill(node.right);
		}

		@Override
		public boolean hasNext() {
			return !queue.isEmpty();
		}

		@Override
		public K next() {
			return queue.poll();
		}

		@Override
		public void remove() {
			
		}
		
	}
}
